package linkedlist;

import java.util.ArrayList;

/**
 * Created with IntelliJ IDEA.
 * Description: 23. 合并 K 个升序链表
 * User: Li_yizYa
 * Date: 2025/5/18
 * Time: 22:11
 */
public class Solution8 {
    /**
     * 每次传入最左边和最右边的链表
     */
    public ListNode mergeKLists2(ListNode[] lists) {
        if (lists == null || lists.length == 0) {
            return null;
        }
        int len = lists.length;
        while (len > 1) {
            int index = 0;
            int left = 0;
            int right = len - 1;
            while (left < right) {
                lists[index++] = merge(lists[left], lists[right]);
                left++;
                right--;
            }
            if (left == right) {
                lists[index++] = lists[left];
            }
            len = index;
        }
        return lists[0];
    }

    /**
     * 每次将相邻的两个链表传入
     */
    public ListNode mergeKLists(ListNode[] lists) {
        if (lists == null || lists.length == 0) {
            return null;
        }
        int len = lists.length;
        while (len > 1) {
            int index = 0;
            for (int i = 0; i < len; i += 2) {
                if (i == len - 1) {
                    lists[index++] = lists[i];
                } else {
                    lists[index++] = merge(lists[i], lists[i + 1]);
                }
            }
            len = index;
        }
        return lists[0];
    }

    /**
     * 每次传入最左边和最右边的链表
     */
    public static ListNode mergeKLists(ArrayList<ListNode> lists) {
        if (lists == null || lists.size() == 0) {
            return null;
        }
        int len = lists.size();
        while (len > 1) {
            int index = 0;
            int left = 0;
            int right = len - 1;
            while (left < right) {
                lists.set(index++, merge(lists.get(left), lists.get(right)));
                left++;
                right--;
            }
            if (left == right) {
                lists.set(index++, lists.get(left));
            }
            len = index;
        }
        return lists.get(0);
    }
    /**
     * 每次将相邻的两个链表传入
     */
    public static ListNode mergeKLists2(ArrayList<ListNode> lists) {
        if (lists == null || lists.size() == 0) {
            return null;
        }
        int len = lists.size();
        while (len > 1) {
            int index = 0;
            for (int i = 0; i < len; i += 2) {
                if (i == len - 1) {
                    lists.set(index++, lists.get(i));
                } else {
                    lists.set(index++, merge(lists.get(i), lists.get(i + 1)));
                }
            }
            len = index;
        }
        return lists.get(0);
    }

    private static ListNode merge(ListNode head1, ListNode head2) {
        if (head1 == null || head2 == null) {
            return head1 == null ? head2 : head1;
        }
        ListNode newHead = new ListNode(-1); // 虚拟节点
        ListNode cur = newHead;
        while (head1 != null && head2 != null) {
            if (head1.val > head2.val) {
                cur.next = head2;
                head2 = head2.next;
                cur = cur.next;
            } else {
                cur.next = head1;
                head1 = head1.next;
                cur = cur.next;
            }
        }
        cur.next = head1 == null ? head2 : head1;
        return newHead.next;
    }

    public static void main(String[] args) {
        ListNode node1 = new ListNode(1);
        ListNode node2 = new ListNode(4);
        ListNode node3 = new ListNode(5);
        node1.next = node2;
        node2.next = node3;
        ArrayList<ListNode> lists = new ArrayList<>();
        lists.add(node1);

        ListNode node4 = new ListNode(1);
        ListNode node5 = new ListNode(3);
        ListNode node6 = new ListNode(4);
        node4.next = node5;
        node5.next = node6;
        lists.add(node4);

        ListNode node7 = new ListNode(2);
        ListNode node8 = new ListNode(6);
        node7.next = node8;
        lists.add(node7);

        ListNode ret = mergeKLists(lists);
        while (ret != null) {
            System.out.print(ret.val + " ");
            ret = ret.next;
        }
    }
}
